import java.util.ArrayList;
import java.util.Comparator;

public class Q148 {
    /*
    给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     */
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode sortList(ListNode head) {
        if(head == null) return head;

        ArrayList<ListNode> list = new ArrayList<>();

        while (head!=null){
            list.add(head);
            head = head.next;
        }

        list.sort(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });

        for(int i=0;i<list.size()-1;i++){
            list.get(i).next = list.get(i+1);
        }
        list.get(list.size()-1).next = null;

        return list.get(0);
    }
}
